#include "stdio.h"
#include "stdlib.h"

typedef int elemtype;
typedef struct TreeNode
{
    elemtype valu;
    struct TreeNode *left;
    struct TreeNode *right;
    struct TreeNode *parent;
} TreeNode, *TreeRoot;

bool CreatTree(TreeRoot parent, TreeRoot &root, elemtype *array, int index)
{
    if (index > *array)
    {
        return false;
    }
    else
    {
        if (*(array + index) == NULL)
        {
            root = NULL;
            return false;
        }
        else
        {
            root = (TreeRoot)malloc(sizeof(TreeNode));
            root->valu = *(array + index);
            root->parent = parent;
            root->left = NULL;
            root->right = NULL;
            CreatTree(root, root->left, array, index * 2);
            CreatTree(root, root->right, array, index * 2 + 1);
            return true;
        }
    }
}
void midvist(TreeRoot root)
{
    if (root)
    {
        midvist(root->left);
        printf("%3d", root->valu);
        midvist(root->right);
    }
}
void midvist2(TreeRoot root)
{
    TreeRoot p = root;
    while (p)
    {
        while (p->left) //访问左子树
        {
            p = p->left;
        }
        printf("%3d", p->valu); //第二次遇到该节点
        if (p->right)           //有有右子树就访问右子树
        {
            p = p->right;
            continue;
        }
        else //左右子树都已经访问完毕
        {
            //当前节点的双亲节点不为空并且当前节点为双亲节点的左节点,说明双亲节点还没有访问
            while (p->parent != NULL && p->parent->left != p)
                /*如果当前节点为双亲节点的右节点，说明双亲节点已经访问完毕

                    回到双亲节点的双亲节点去，知道当前双亲节点为空或者为左子树*/
                p = p->parent;
            //回到双亲节点来
            p = p->parent;
            //这里需要判断当前节点是否为空，因为在访问最后一个节点的时候上面一步会不断地循环到双亲节点，直到最后循环到根节点的双亲节点 -->NULL
            if (p)
            {
                printf("%3d", p->valu);
                p = p->right;
            }
        }
    }
}
void main()
{
    int a[] = {15,
               1,
               2, 3,
               4, 6, NULL, 7,
               NULL, NULL, 10, 11, NULL, NULL, 14, 15};
    TreeRoot Btree;
    CreatTree(NULL, Btree, a, 1);
    midvist(Btree);
    printf("\n");
    midvist2(Btree);
    printf("\n");
}